package leetcode.editor.cn.q2xx

import kotlin.math.min

class Q264 {
    fun nthUglyNumber(n: Int): Int {
        val dp = IntArray(n+1)
        dp[1] = 1
        var p2 = 1
        var p3 = 1
        var p5 = 1
        for (i in 2..n) {
            val n2 = dp[p2] * 2
            val n3 = dp[p3] * 3
            val n5 = dp[p5] * 5
            dp[i] = min(n2, min(n3,n5))
            println("${dp[i]} $n2 $n3 $n5 ${dp[p2]} ${dp[p3]} ${dp[p5]} ")
            if (dp[i]==n2)
                p2++
            if (dp[i]==n3)
                p3++
            if (dp[i]==n5)
                p5++
        }
        return dp[n]
    }
}

fun main() {
    val sol = Q264()
    println(sol.nthUglyNumber(10))
}